package algorithms;

import java.util.Arrays;
import java.util.Random;

import algorithms.heap.LeftistMinHeap;
import algorithms.heap.SkewHeap;
import algorithms.tree.BinaryNode;
import algorithms.tree.BinarySearchTree;
import algorithms.tree.Tree;

public class Util {

	private Util() {
	}

	/**
	 * 打印数组内容
	 * 
	 * @param array
	 */
	public static <T> void print(T[] array) {
		StringBuilder sb = new StringBuilder();
		int count = 0;
		for (T i : array) {
			sb.append(i.toString()).append(++count % 20 == 0 ? "\n" : ",");
		}
		System.out.println(sb.toString().substring(0, sb.length() - ",".length()));
	}

	/**
	 * 打印数组内容，限定打印数量
	 * 
	 * @param array
	 */
	public static <T> void print(T[] array, int size) {
		StringBuilder sb = new StringBuilder();
		int count = 0;
		for (T i : array) {
			sb.append(i.toString()).append(++count % 20 == 0 ? "\n" : " ");
			if (count > size) {
				sb.append("...");
				break;
			}
		}
		System.out.println(sb.toString() + "\n-------");
	}

	public static void printTree(Tree<?, ?> tree) {
		System.out.println("中序：" + tree.inorderTraversing());
		System.out.println("前序：" + tree.preorderTraversing());
		System.out.println("后序：" + tree.postorderTraversing());
	}

	/**
	 * 生成长度为size的随机Integer数组，最大值为size<<2或Integer.MAX_VALUE
	 * 
	 * @param size
	 * @return
	 */
	public static Integer[] generateArray(int size) {
		Integer[] result = new Integer[size];
		Random random = new Random();
		int max = size << 2 < 0 ? Integer.MAX_VALUE : size << 2;
		for (int i = 0; i < result.length;) {
			result[i++] = random.nextInt(max);
		}
		return result;
	}

	/**
	 * 拷贝Integer数组
	 * 
	 * @param array
	 * @return
	 */
	public static Integer[] getArrayCopy(Integer[] array) {
		return Arrays.copyOf(array, array.length);
	}

	public static BinarySearchTree<Integer> generateBST(Integer[] a) {
		BinarySearchTree<Integer> tree = new BinarySearchTree<>();
		for (Integer i : a) {
			BinaryNode<Integer> node = new BinaryNode<Integer>(i);
			tree.insertNode(node);
		}
		return tree;
	}

	/**
	 * 交换数组内两个元素
	 * 
	 * @param a
	 * @param i
	 * @param j
	 */
	public static <T> void exchange(T[] a, int i, int j) {
		T tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	/**
	 * 指定数组内元素范围，间隔为step的元素，按指定step平移（向右）
	 * 
	 * @param a
	 * @param beginIndex
	 * @param endIndex
	 * @param step
	 */
	public static <T> void rightMove(T[] a, int beginIndex, int endIndex, int step) {
		for (int i = endIndex + step; i > beginIndex;) {
			a[i] = a[i -= step];
		}
	}

	/*
	 * 在有序列表中使用二分查找法查找某个值的位置，不存在则返回大于它的第一个值的位置
	 */
	public static <T extends Comparable<T>> int binarySearch(T[] a, T value, int left, int right) {
		// value不在有序序列范围内
		if (value.compareTo(a[right]) > 0) {
			return right + 1;
		}
		if (value.compareTo(a[left]) < 0) {
			return -1;
		}
		// System.out.println("index range:[" + left + "," +
		// right + "]");
		int mid = (left + right) >> 1;
		if (left < right && mid < right && mid > left) {
			if (a[mid].compareTo(value) > 0) {
				right = mid;
			} else if (a[mid].compareTo(value) < 0) {
				left = mid;
			} else {
				return mid;
			}
			return binarySearch(a, value, left, right);
		}

		return right;
	}

	/**
	 * 检查数组是否是单调增的（升序）
	 * 
	 * @param array
	 * @return
	 */
	public static <T extends Comparable<T>> boolean isArrayMonotoneIncreasing(T[] array) {
		int i = 0;
		while (i < array.length - 1) {
			if (array[i].compareTo(array[++i]) > 0) {
				System.out.println("index:" + i + "value:" + array[i] + ",next value:" + array[i + 1]);
				return false;
			}
		}
		return true;

	}

	public static LeftistMinHeap generateLeftMinHeap(Integer[] a) {
		LeftistMinHeap heap = new LeftistMinHeap();
		for (int i : a) {
			heap.merge(new LeftistMinHeap.LeftistBinaryNode(i));
		}
		return heap;
	}

	public static SkewHeap generateSkewHeap(Integer[] a) {
		SkewHeap heap = new SkewHeap();
		for (int i : a) {
			heap.merge(new BinaryNode<Integer>(i));
		}
		return heap;
	}
}
